package 面试题52_两个链表的第一个公共节点;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 13:04 2021/3/19
 * @Description：
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == null && headB == null) return null;
        if (headA == null || headB == null) return null;

        int lengthA = getLinkedListLength(headA);
        int lengthB = getLinkedListLength(headB);

        ListNode pHeadLong = headA;
        ListNode pHeadShort = headB;

        if (lengthA < lengthB) {
            pHeadLong = headB;
            pHeadShort = headA;
        }

        ListNode pNodeLong = pHeadLong;
        ListNode pNodeShort = pHeadShort;

        for (int i = 0; i < Math.abs(lengthA - lengthB); i++) {
            pNodeLong = pNodeLong.next;
        }

        while (pNodeLong != null && pNodeShort != null) {
            if (pNodeShort == pNodeLong) {
                return pNodeShort;
            }
            pNodeLong = pNodeLong.next;
            pNodeShort = pNodeShort.next;
        }

        return null;
    }

    int getLinkedListLength(ListNode head) {
        int length = 0;

        ListNode pNode = head;
        while (pNode != null) {
            length++;

            pNode = pNode.next;
        }

        return length;
    }
}
